The present invention relates generally to systems and methods for processing digital data. In particular, it pertains to a system and method for performing wavelet and inverse wavelet transformations of digital data using semi-orthogonal wavelets.
The use of IWTs (integral wavelet transforms) and inverse IWTs is well established in MRA (multi-resolution analysis) processing of 1-D (one dimensional) digital data, such as audio signals, and/or 2-D (two dimensional) digital data, such as image data. A special feature of IWTs and inverse IWTs is that they provide narrow windowing of short duration high frequency data while also providing wide windowing of long duration low frequency data. This is generally described in Chui, C. K., xe2x80x9cAn Introduction to Waveletsxe2x80x9d, Academic Press, Boston, Mass., 1992, which is hereby incorporated by reference. The following discussion provides examples of how IWTs and inverse IWTs have been implemented in the past.
Wavelet Transform System using Dual Wavelets {{overscore (xcexa8)}m,km(x)} as Basic Wavelets
FIG. 1 shows a 1-D wavelet transform system 100, which is an improved version of the wavelet transform system shown in An Introduction to Wavelets. This system 100 incorporates some aspects of the present invention, but first we will first explain the conventional aspects of this system. The wavelet transform system 100 implements a 1-D IWT that, for each resolution level m at which a decomposition is made, uses dual wavelets {{overscore (xcexa8)}m,km(x)} to corresponding standard wavelets {xcexa8m,km(x)} as the basic wavelets in the 1-D IWT and uses dual scaling functions {{overscore (xcfx86)}m,km(x)} to corresponding standard scaling functions {xcfx86m,km(x)} as the basic scaling functions in the 1-D IWT. Each standard wavelet xcexa8m,km(x) and standard scaling function xcfx86m,km(x) is given by:                                                         Ψ                              m                ,                                  k                  m                                                      ⁡                          (              x              )                                =                                    2                              m                /                2                                      ⁢                          Ψ              ⁡                              (                                                                            2                      m                                        ⁢                    x                                    -                                      k                    m                                                  )                                                    ⁢                  
                ⁢                                            φ                              m                ,                                  k                  m                                                      ⁡                          (              x              )                                =                                    2                              m                /                2                                      ⁢                          φ              ⁡                              (                                                                            2                      m                                        ⁢                    x                                    -                                      k                    m                                                  )                                                                        (        1        )            
where km is a corresponding index for the resolution level m and the normalization factor 2m/2 will be suppressed hereafter for computational efficiency.
In performing the 1-D IWT, the wavelet transform system 100 decomposes a 1-D set of original data samples fM at an original resolution level m=M into a 1-D set of standard scaling function coefficients CN in an L (low) frequency band at the resolution level m=N and 1-D sets of standard wavelet coefficients dMxe2x88x921 to dN in H (high) frequency bands at respectively the resolution levels m=Mxe2x88x921 to N.
The set of original data samples fM={fM,n}=fM(2xe2x88x92Mn) is given by a 1-D function fM(x), where x=2xe2x88x92Mn. The 1-D function fM(x) approximates another 1-D function f(x) at the original resolution level M. The set of original data samples fM extends in one spatial dimension, namely the x direction, and is first pre-processed by a pre-decomposition filter 102 of the 1-D wavelet transform system 100. The pre-decomposition filter has a transfer function xcfx86(z)xe2x88x921 for mapping (i.e., converts) the 1-D set of original data samples fM into a 1-D set of standard scaling function coefficients CM in an L frequency band at the original resolution level M.
The transfer function xcfx86(z)xe2x88x921 is obtained from the following relationship at the resolution level m between a 1-D function fm(x), the standard scaling functions {xcfx86m,km(x)} and the set of standard scaling function coefficients cm={cm,km}:                                           f            m                    ⁡                      (            x            )                          =                              ∑                          k              m                                ⁢                                    c                              m                ,                                  k                  m                                                      ⁢                                          φ                                  m                  ,                                      k                    m                                                              ⁡                              (                x                )                                                                        (        2        )            
where the 1-D function fm(x) approximates the function f(x) at the resolution level m. The transfer function xcfx86(z)xe2x88x921 is the inverse of a transfer function xcfx86(z). The transfer function xcfx86(z) is a polynomial that has the sequence of mapping coefficients {xcfx86n}={xcfx860,0(n)} as its coefficients while the transfer function xcfx86(z)xe2x88x921 is a rational function that has a corresponding sequence of mapping coefficients {"THgr"n} as its poles. Thus, the pre-decomposition filter 102 comprises a 1-D IIR (infinite impulse response) filter that applies the sequence of mapping coefficients {"THgr"n} to the set of original data samples fM={fM,n} to generate the set of standard scaling function coefficients CM={CM,km}.
Then, the decomposition filter 104 of the 1-D wavelet transform system 100 decomposes the set of standard scaling function coefficients CM into the sets of standard scaling function and wavelet coefficients CN and dMxe2x88x921 to dN. To do this, in the present invention the decomposition filter 104 has a corresponding decomposition filter stage 106 for each resolution level m=M to N+1 at which a decomposition is made. The decomposition filter stage 106 for each resolution level m decomposes a 1-D set of standard scaling function coefficients cm in an L frequency band at the higher resolution level m into a 1-D set of standard scaling function coefficients cmxe2x88x921 in an L frequency band and a 1-D set of wavelet coefficients dmxe2x88x921 in an H frequency band at the next lower resolution level mxe2x88x921.
This is done by the decomposition filter stage 106 according to the function fm(x) given in Eq. (2). Here, for each resolution level m, the function fm(x) further provides the following relationship between the set of standard scaling function coefficients cm at each resolution level m and the sets of standard scaling function and wavelet coefficients cmxe2x88x921={cmxe2x88x921,kmxe2x88x921} and dmxe2x88x921={dmxe2x88x921,kmxe2x88x921} at the next lower resolution level mxe2x88x921:                                                                                          ∑                                      k                    m                                                  ⁢                                                      c                                          m                      ,                                              k                        m                                                                              ⁢                                                            φ                                              m                        ,                                                  k                          m                                                                                      ⁡                                          (                      x                      )                                                                                  =                              xe2x80x83                            ⁢                                                                    ∑                                          k                                              m                        -                        1                                                                              ⁢                                                            d                                                                        m                          -                          1                                                ,                                                  k                                                      m                            -                            1                                                                                                                ⁡                                          (                      x                      )                                                                      +                                                                                                        xe2x80x83                            ⁢                                                c                                                            m                      -                      1                                        ,                                          k                                              m                        -                        1                                                                                            ⁢                                                                            φ                                                                        m                          -                          1                                                ,                                                  k                                                      m                            -                            1                                                                                                                ⁡                                          (                      x                      )                                                        .                                                                                        (        3        )            
In Eq. (3), the set of standard scaling function coefficients {cmxe2x88x921,kmxe2x88x921} has the indexes {kmxe2x88x921}={(kmxe2x88x921)/2} for odd indexes {km} and the set of standard wavelet coefficients {dmxe2x88x921,kmxe2x88x921} has the indexes {kmxe2x88x921}={km/2} for even indexes {km}.
Furthermore, there exists two 1-D sequence of decomposition coefficients {an} and {bn} such that each standard scaling function xcfx86m,km(x) at a higher resolution level m is related to and can be decomposed into the standard wavelets and scaling functions {xcexa8m,km(x)} and {xcfx86m,km(x)} at the next lower resolution level mxe2x88x921. This decomposition relation is given as follows:                                                                                           φ                                      m                    ,                                          k                      m                                                                      ⁡                                  (                  x                  )                                            =                              xe2x80x83                            ⁢                                                                    ∑                                          k                                              m                        -                        1                                                                              ⁢                                                            a                                                                        k                          m                                                -                                                  2                          ⁢                                                      k                                                          m                              -                              1                                                                                                                                            ⁢                                          φ                                                                        m                          -                          1                                                ,                                                  k                                                      m                            -                            1                                                                                                                ⁢                                          (                      x                      )                                                                      +                                                                                                        xe2x80x83                            ⁢                                                b                                                            k                      m                                        -                                          2                      ⁢                                              k                                                  m                          -                          1                                                                                                                    ⁢                                                                            Ψ                                                                        m                          -                          1                                                ,                                                  k                                                      m                            -                            1                                                                                                                ⁡                                          (                      x                      )                                                        .                                                                                        (        4        )            
In view of Eqs. (3) and (4), the sets of standard scaling function and wavelet coefficients {cmxe2x88x921,kmxe2x88x921} and {dmxe2x88x921,kmxe2x88x921} at the resolution level mxe2x88x921 are obtained according to the decomposition sequences:                                           c                                          m                -                1                            ,                              k                                  m                  -                  1                                                              =                                    ∑                              k                m                                      ⁢                                          a                                                      k                    m                                    -                                      2                                          k                                              m                        -                        1                                                                                                        ⁢                              c                                  m                  ,                                      k                    m                                                                                      ⁢                  
                ⁢                              d                                          m                -                1                            ,                              k                                  m                  -                  1                                                              =                                    ∑                              k                m                                      ⁢                                          b                                                      k                    m                                    -                                      2                    ⁢                                          k                                              m                        -                        1                                                                                                        ⁢                                                c                                      m                    ,                                          k                      m                                                                      .                                                                        (        5        )            
it must be noted here that the dual wavelets {{overscore (xcexa8)}m,km(x)} and the dual scaling functions {{overscore (xcfx86)}m,km(x)} are used respectively as the basic wavelets and scaling functions in the 1-D IWT since the 1-D IWT is defined by:                                           c                          m              ,                              k                m                                              =                                    ∫                              -                ∞                            ∞                        ⁢                                          f                ⁡                                  (                  x                  )                                            ⁢                                                                    φ                    _                                                        m                    ,                                          k                      m                                                                      ⁡                                  (                  x                  )                                            ⁢                              xe2x80x83                            ⁢                              ⅆ                x                                                    ⁢                  
                ⁢                              d                          m              ,                              k                m                                              =                                    ∫                              -                ∞                            ∞                        ⁢                                          f                ⁡                                  (                  x                  )                                            ⁢                                                                    Ψ                    _                                                        m                    ,                                          k                      m                                                                      ⁡                                  (                  x                  )                                            ⁢                                                ⅆ                  x                                .                                                                        (        6        )            
Thus, the transfer functions A(z) and B(z) of the decomposition filter stage 106 are polynomials that respectively have the sets of decomposition coefficients {an} and {bn} as their coefficients.
As is well known, when the standard wavelets {xcexa8m,km(X)} are s.o. wavelets, the dual wavelets {{overscore (xcexa8)}m,km(x)} are also s.o. wavelets. In this case, the sequences of decomposition coefficients {an} and {bn} are infinite. This is described in detail for a subset of s.o. wavelets known as spline wavelets in An introduction to Wavelets and in Chui, C. K. et al., xe2x80x9cSpline-Wavelet Signal Analyzers and Method for Processing Signalsxe2x80x9d, U.S. Pat. No. 5,262,958, issued Nov. 16, 1993, which is hereby incorporated by reference.
Referring to FIG. 2, when the standard wavelets {xcexa8m,km(x)} are s.o. wavelets, the sequences of coefficients may be truncated {an} and {bn} in order to use FIR (finite impulse response) filters 108 and 110 in the decomposition filter stage 106 for each resolution level m, as described in U.S. Pat. No. 5,262,958. The filters 108 and 110 respectively perform the transfer functions A(z) and B(z) on the set of standard scaling function coefficients cm at the resolution level m. This is done by applying the sequences of decomposition coefficients {an} and {bn} to the set of standard scaling function coefficients cm={cm,km} to respectively generate sets of intermediate coefficients {cmxe2x88x921,km} and {dmxe2x88x921,km}. The sets of intermediate coefficients {cmxe2x88x921,km} and {dmxe2x88x921,km} are then downsampled by the downsamplers 112 of the decomposition filter stage 106 to respectively generate the sets of standard scaling function and wavelet coefficients cmxe2x88x921={cmxe2x88x921,km} and dmxe2x88x921={dmxe2x88x921,kmxe2x88x921} at the resolution level mxe2x88x921.
Inverse Wavelet Transform System using Standard Wavelets {xcexa8m,km(x)} as Basic Wavelets
Conversely, FIG. 3 shows an inverse wavelet transform system 120 corresponding to the system shown in FIG. 1. The wavelet transform system 120 implements a corresponding 1-D inverse IWT to the 1-D IWT just described. Thus, the standard scaling functions and wavelets {xcfx86m,km(x)} and {xcexa8m,km(x)} are used as the basic scaling functions and wavelets in the 1-D inverse IWT to reconstruct the 1-D sets of standard scaling function and wavelet coefficients cN and dMxe2x88x921 to dN into a 1-D set of reconstructed data samples fM.
In order to do so, the reconstruction filter 122 of the inverse wavelet transform system 120 first reconstructs the 1-D set of standard scaling function and wavelet coefficients cN and dMxe2x88x921 to dN into the 1-D set of standard scaling function coefficients cM. In particular, for each resolution level m=N to Mxe2x88x921 at which a reconstruction is made, the reconstruction filter 122 has a corresponding reconstruction filter stage 124 that reconstructs the sets of standard scaling function and wavelet coefficients cm and dm in the L and H frequency bands at the lower resolution level m into the set of standard scaling function coefficients cm+1 in the L frequency band at the next higher resolution level m+1.
This is done by the reconstruction filter stage 124 for each resolution level m with two 1-D sequences of reconstruction coefficients {pn} and {qn}. Here, in one two-scale relation, each standard scaling function xcfx86m,km(x) at a lower resolution level m is related to and can be reconstructed into the standard scaling functions {xcfx86m+1,km+1(x)} at the next higher resolution level m+1 with the sequence of reconstruction coefficients {pn}. Similarly, in another two-scale relation, each standard wavelet xcexa8m,km(x) at a lower resolution level m is related to and can be reconstructed into the standard scaling functions {xcfx86m+1,km+1} at the next higher resolution level m+1 with the sequence of reconstruction coefficients {qn}. These two-scale relations are given by:                                                         φ                              m                ,                                  k                  m                                                      ⁡                          (              x              )                                =                                    ∑                              k                                  m                  +                  1                                                      ⁢                                          p                                  k                                      m                    +                    1                                                              ⁢                                                φ                                                            m                      +                      1                                        ,                                                                  2                        ⁢                                                  k                          m                                                                    +                                              k                                                  m                          +                          1                                                                                                                    ⁡                                  (                  x                  )                                                                    ⁢                  
                ⁢                                                            Ψ                                  m                  ,                  k                                            m                        ⁡                          (              x              )                                =                                    ∑                              k                                  m                  +                  1                                                      ⁢                                          q                                  k                                      m                    +                    1                                                              ⁢                                                                    φ                                                                  m                        +                        1                                            ,                                                                        2                          ⁢                                                      k                            m                                                                          +                                                  k                                                      m                            +                            1                                                                                                                                ⁡                                      (                    x                    )                                                  .                                                                        (        7        )            
From Eqs. (3) and (7), each scaling function coefficient cm+1,km+1 is obtained according to the reconstruction sequence:                               c                                    m              +              1                        ,                          k                              m                +                1                                                    =                              ∑                          k              m                                ⁢                                    (                                                                    p                                                                  k                                                  m                          -                          1                                                                    -                                              2                        ⁢                                                  k                          m                                                                                                      ⁢                                      c                                          m                      ,                                              k                        m                                                                                            +                                                      q                                                                  k                                                  m                          +                          1                                                                    -                                              2                        ⁢                                                  k                          m                                                                                                      ⁢                                      d                                          m                      ,                                              k                        m                                                                                                        )                        .                                              (        8        )            
By combining Eqs. (3) and (8), it can be seen that the standard scaling functions and wavelets {xcfx86m,km(x)} and {xcexa8m,km(x)} are used as the basic scaling functions and wavelets in the 1-D inverse IWT.
As described in xe2x80x9cAn Introduction to Waveletsxe2x80x9d and U.S. Pat. No. 5,262,958, the sequences of reconstruction coefficients {pn} and {qn} are finite when the standard wavelets {xcexa8m,km(x)} are the basic wavelets in the 1-D inverse IWT and are spline wavelets. Similar to the corresponding 1-D IWT, this is also true for the more general case where the standard wavelets {xcexa8m,kk(x)} are s.o. wavelets.
Therefore, in the case where semi-orthgonal standard wavelets {xcexa8m,km(x)} are used in the 1-D inverse IWT, each reconstruction filter stage 124 has transfer functions P(z) and Q(z). These transfer functions P(z) and Q(z) are polynomials that respectively have the sets of decomposition coefficients {pn} and {qn} as their coefficients.
Referring to FIG. 4, in order to perform the transfer functions P(z) and Q(z), the reconstruction filter stage 124 at each resolution level m has upsamplers 126. The upsamplers 126 respectively upsample the sets of scaling function and wavelet coefficients cm={cm,km} and dm={dm,km} at the resolution level m to respectively generate the sets of intermediate coefficients {cm,kmxe2x88x921} and {dm,kmxe2x88x921}.
The reconstruction filter stage 124 at each resolution level m also includes FIR filters 130 and 132. The filters 130 and 132 respectively perform the transfer functions P(z) and Q(z) by applying the sequences of decomposition coefficients {pn} and {qn} respectively to the sets of intermediate coefficients {cm,km+1} and {dm,km+1} to respectively generate the sets of intermediate coefficients {ym+1,km} and {zm+1,km}. The sets of intermediate coefficients {ym+1,km+1} and {zm+1,km+1} are then component-wise summed (i.e., each intermediate coefficient ym+1,km+1 is summed with the corresponding intermediate coefficient zm+1,km+1) by the summing stage 134 to generate the set of standard scaling function coefficients cm+1={cm+1,km+1} at the resolution level m+1.
Referring back to FIG. 3, the post-reconstruction filter 136 of the inverse wavelet transform system 120 then maps the set of standard scaling function coefficients cM into the set of reconstructed data samples fM in accordance with Eq. (2). The post-reconstruction filter 136 comprises an FIR filter and has a transfer function xcfx86(z) that is the inverse of the transfer function xcfx86(z)xe2x88x921 of the pre-decomposition filter 102. Thus, the sequence of coefficients {xcfx86n} are applied to the set of standard scaling function coefficients cM to generate the set of reconstructed data samples fM.
Wavelet Transform System using S.O. Standard Wavelets {xcexa8m,km(x)} as Basic Wavelets
FIG. 5 shows a 1-D wavelet transform system 140 in which standard scaling function {xcfx86m,km(x)} and s.o. standard wavelets {xcexa8m,km(x)} are used as the basic scaling functions and wavelets in the 1-D IWT. As will be explained shortly, this is done in order to take advantage of the fact that the finite sequences of coefficients {pn} and {qn} are used as the sequences of decomposition coefficients in this 1-D IWT instead of the infinite sequences of coefficients {an} and {bn}. This concept is described in Chui, C. K. et al., U.S. Pat. No. 5,600,373, entitled xe2x80x9cMethod and Apparatus for Video Image Compression and Decompression Using Boundary-Spline-Waveletsxe2x80x9d, issued Feb. 4, 1997, which is hereby incorporated by reference, for the specific case where the standard wavelets {xcexa8m,km(x)} are boundary spline wavelets in a 2-D IWT which uses banded matrices for the sequences of coefficients {pn} and {qn}. However, in accordance with the present invention, it may be extended to the more general case where the standard wavelets {xcexa8m,km(x)} are semi-orthogonal wavelets. For simplicity, this more general case will be described hereafter for the 1-D IWT.
Like the 1 D wavelet transform system 100 described earlier, the 1-D wavelet transform system 140 includes a pre-decomposition filter 142. However, the pre-decomposition filter 142 has a transfer function xcfx86(z)xe2x88x921xcex1(z) for mapping the 1-D set of original data samples fM into a 1-D set of dual scaling function coefficients {overscore (c)}M in an L frequency band at the resolution level M.
Referring to FIG. 6, in order to do this, the pre-decomposition filter 142 of the present invention includes as a mapping filter stage 102 the same pre-decomposition filter 102 as that shown in FIG. 1. Thus, with the transfer function xcfx86(z)xe2x88x921, this mapping filter stage 102 maps the set of original data samples fM into the set of standard scaling function coefficients cM.
The pre-decomposition filter 142 of the present invention also has a mapping filter stage 144 that maps the set of standard scaling function coefficients cM to the set of dual scaling function coefficients {overscore (c)}M. This generates a change of bases so that the standard scaling functions {xcfx86m,km(x)} and the semi-orthogonal standard wavelets {xcexa8m,km(x)} are used as the basic scaling functions and wavelets in the 1-D IWT instead of the dual scaling functions and wavelets {{overscore (xcfx86)}m,km(x)} and {{overscore (xcexa8)}m,km(x)}.
In order to do this, it is important to note that the 1-D function fm(x) given in Eq. (2) is also related to the dual scaling functions {{overscore (xcfx86)}m,km(x)} and a 1-D set of dual scaling function coefficients {overscore (c)}m={{overscore (c)}m,km} at the resolution level m according to the following relationship:                                           f            m                    ⁡                      (            x            )                          =                              ∑                          k              m                                ⁢                                                    c                _                                            m                ,                                  k                  m                                                      ⁢                                                                                φ                    _                                                        m                    ,                                          k                      m                                                                      ⁡                                  (                  x                  )                                            .                                                          (        9        )            
Moreover, each dual scaling function coefficient {overscore (c)}m,km and the set of standard scaling function coefficients {cm,km} are related by a sequence of mapping coefficients {xcex1n} as follows:                               c                      m            ,                          k              m                                      =                              ∑            n                    ⁢                                    α              n                        ⁢                          c                              m                ,                                                      k                    m                                    -                  n                                                                                        (        10        )            
where each mapping coefficient xcex1n is given by the following change of bases formula:                               α          n                =                              ∫                          -              ∞                        ∞                    ⁢                                                    φ                                  m                  ,                  0                                            ⁡                              (                x                )                                      ⁢                                          φ                                  m                  ,                  n                                            ⁡                              (                x                )                                      ⁢                                          ⅆ                x                            .                                                          (        11        )            
The transfer function xcex1(z) for the mapping filter stage 144 is a polynomial that has the sequence of mapping coefficients {xcex1n} as its coefficients. Thus, for m=M in Eqs. (9) to (11), the mapping filter stage 144 is an FIR filter and performs the transfer function xcex1(z) by applying the sequence of mapping coefficients {xcex1n} to the set of standard scaling function coefficients cM={cM,kM} to generate the set of dual scaling function coefficients {overscore (c)}M={cM,kM}.
Then, referring back to FIG. 5, the decomposition filter 146 of the 1-D wavelet transform system 140 decomposes the 1-D set of dual scaling function coefficients {overscore (c)}M in the L frequency band at the original resolution level M into a 1-D set of dual scaling function coefficients {overscore (c)}N in an L frequency band at the resolution level N and 1-D sets of dual wavelet coefficients {overscore (d)}Mxe2x88x921 to {overscore (d)}N in H frequency bands at respectively the resolution levels Mxe2x88x921 to N. To do so, the decomposition filter 146 has a corresponding decomposition filter stage 148 for each resolution level m=M to N+1 at which a decomposition is made. The decomposition filter stage 148 for each resolution level m decomposes a 1-D set of dual scaling function coefficients {overscore (c)}m in an L frequency band at the higher resolution level m into a 1-D set of dual scaling function coefficients {overscore (c)}mxe2x88x921 in an L frequency band and a 1-D set of dual wavelet coefficients {overscore (d)}mxe2x88x921 in an H frequency band at the next lower resolution level mxe2x88x921.
This is done in view of the fact that, when a change of bases is made and the standard scaling functions {xcfx86m,km(x)} and the semi-orthogonal standard wavelets {xcexa8m,km(x)} are used as the basic scaling functions and wavelets in the 1-D IWT, the relationships in Eqs. (1) to (8) are switched (i.e., interchanged) with those for when the dual scaling functions and wavelets {{overscore (xcfx86)}m,km(x)} and {{overscore (xcexa8)}m,km(x)} are the basic wavelets in the 1-D IWT. More specifically, at each resolution level M, the standard scaling functions {xcfx86m,km(x)} and the semi-orthogonal standard wavelets {xcexa8m,km(x)} are respectively switched with the corresponding dual scaling functions and wavelets {{overscore (xcfx86)}m,km(x)} and {{overscore (xcexa8)}m,km(x)}, the sets of standard scaling function and wavelet coefficients cm, cmxe2x88x921, and dmxe2x88x921 are respectively switched with the corresponding sets of dual scaling function and wavelet coefficients {overscore (c)}m, {overscore (c)}mxe2x88x921, and {overscore (d)}mxe2x88x921, and the sequences of coefficients {an} and {bn} are respectively switched with the sequences of coefficients {pn} and {qn}. This is further described in An Introduction to Wavelets.
Thus, the decomposition filter stage 148 at each resolution level m has the transfer functions P(z) and Q(z). The decomposition filter stage 148 performs the transfer functions P(z) and Q(z) on the set of dual scaling function coefficients {overscore (c)}m to generate the sets of dual wavelet and scaling functions coefficients {overscore (c)}mxe2x88x921 and {overscore (d)}mxe2x88x921.
More specifically, as shown in FIG. 7, in accordance with the present invention the decomposition filter stage 148 at each resolution level m has the same filters 130 and 132 as those shown in FIG. 4 for each reconstruction filter stage 124 of the inverse wavelet transform system 120 of FIG. 3. In this case, the filter stages 130 and 132 respectively perform the transfer functions P(z) and Q(z) (which are generally shorter, and thus more computationally efficient, than A(z) and B(z) of the system shown in FIG. 1) by respectively applying the sequences of decomposition coefficients {pn} and {qn} to the set of dual scaling function coefficients {overscore (c)}m={{overscore (c)}m,km} to respectively generate the sets of dual wavelet and scaling functions coefficients {{overscore (d)}mxe2x88x921,km} and {{overscore (c)}mxe2x88x921,km} The sets of dual wavelet and scaling functions coefficients {{overscore (d)}mxe2x88x921,km} and {{overscore (c)}mxe2x88x921,km} are then respectively downsampled by the downsamplers 112 of the decomposition filter stage 146 to respectively generate the sets of standard wavelet and scaling functions coefficients {overscore (d)}mxe2x88x921={{overscore (d)}mxe2x88x921,kmxe2x88x921} and {overscore (c)}mxe2x88x921={{overscore (c)}mxe2x88x921,kmxe2x88x921}. The downsamplers 112 are the same as those shown in FIG. 2 for each decomposition filter stage 106 of the wavelet transform system 100 of FIG. 1.
Inverse Wavelet Transform System using Standard Wavelets {xcexa8m,km(x)} as Basic Wavelets
FIG. 8 shows an inverse wavelet transform system 160 that implements a corresponding 1-D inverse IWT to the 1-D IWT implemented by the wavelet transform system 140 of FIG. 5. Like the 1-D inverse IWT performed by the inverse wavelet transform system 120 of FIG. 3, the 1-D inverse IWT implemented by the inverse wavelet transform system 160 uses the standard scaling functions {xcfx86m,km(x)} and the semi-orthogonal standard wavelets {xcexa8m,km(x)} as the basic scaling functions and wavelets in the 1-D inverse IWT.
In order to implement the 1-D inverse IWT, the inverse wavelet transform system 160 includes a reconstruction filter 162. The reconstruction filter 162 reconstructs the sets of dual scaling function and wavelet coefficients {overscore (c)}N and {overscore (d)}Mxe2x88x921 to {overscore (d)}N into the set of standard scaling function coefficients CM. In order to do so, the reconstruction filter 162 includes a corresponding reconstruction filter stage 163 for the first resolution level m=N at which a reconstruction is made and a corresponding reconstruction filter stage 164 for every other resolution level m=N+1 to Mxe2x88x921 at which a reconstruction is made. The reconstruction filter stage 163 has the transfer functions Q(z)xcex2(z)xe2x88x921 and P(z)xcex1(z)xe2x88x921 while each reconstruction filter stage 164 has the transfer functions Q(z)xcex2(z)xe2x88x921 and P(z).
Referring to FIG. 9, the reconstruction filter stage 163 includes a mapping filter substage 166 which has the transfer function xcex1(z)xe2x88x921. The mapping filter substage 166 uses the transfer function xcex1(z)xe2x88x921 to map the set of dual scaling function coefficients {overscore (c)}N to the set of standard scaling function coefficients cN at the resolution level N. Furthermore, referring to FIGS. 9 and 10, each reconstruction filter 163 and 164 includes a mapping filter substage 168 that has a transfer function xcex2(z)xe2x88x921 for mapping the set of dual wavelet coefficients {overscore (d)}m to the set of standard wavelet coefficients dm at the corresponding resolution level m. In this way, a change of bases is made so that the standard scaling functions {xcfx86m,km(x)} and the semi-orthogonal standard wavelets {xcexa8m,km(x)} are used as the basic scaling functions and wavelets in the 1-D inverse IWT rather than the dual scaling functions and wavelets {{overscore (xcfx86)}m,km(x)} and {{overscore (xcexa8)}m,km(x)}.
Referring back to FIG. 9, the transfer function xcex1(z)xe2x88x921 of the mapping filter substage 166 is the inverse of the transfer function xcex1(z) described earlier. Thus, the transfer function xcex1(z)xe2x88x921 is a rational function which has a sequence of mapping coefficients {xcex94n} as its poles. Thus, the mapping filter substage 166 is an IIR filter that applies the sequence of mapping coefficients {xcex94n} to the set of dual scaling function coefficients {overscore (c)}N to generate the set of standard scaling function coefficients cN.
Moreover, turning again to FIGS. 9 and 10, the transfer function xcex2(z)xe2x88x921 for each mapping filter substage 168 is determined in view of the following relationship at the corresponding resolution level m:                                           ∑                          k              m                                ⁢                                    d                              m                ,                                  k                  m                                                      ⁢                                          ψ                                  m                  ,                                      k                    m                                                              ⁡                              (                x                )                                                    =                              ∑                          k              m                                ⁢                                                    d                ~                                            m                ,                                  k                  m                                                      ⁢                                                                                ψ                    ~                                                        m                    ,                                          k                      m                                                                      ⁡                                  (                  x                  )                                            .                                                          (        12        )            
Furthermore, at this resolution level m-1, there exists a sequence of mapping coefficients {xcex2n} such that:                                                         d              ~                                      m              ,                              k                m                                              ⁡                      (            x            )                          =                              ∑            n                    ⁢                                    β              n                        ⁢                                          d                                  m                  ,                                                            k                      m                                        -                    n                                                              ⁡                              (                x                )                                                                        (        13        )            
where each mapping coefficient xcex2n is given by:                               β          n                =                              ∫                          -              ∞                        ∞                    ⁢                                                    ψ                                  m                  ,                  0                                            ⁡                              (                x                )                                      ⁢                                          ψ                                  m                  ,                  n                                            ⁡                              (                x                )                                      ⁢                                          ⅆ                x                            .                                                          (        14        )            
The transfer function xcex2(z)xe2x88x921 is the inverse of a transfer function xcex2(z). The transfer function xcex2(z) is a polynomial that has the sequence of mapping coefficients {xcex2n} as its coefficients. Thus, the transfer function xcex2(z)xe2x88x921 is a rational function which has a corresponding sequence of mapping coefficients {xcex4n} as its poles. As result, the mapping filter substage 168 is an IIR filter and applies the sequence of mapping coefficients {xcex4n} to the set of dual wavelet coefficients {overscore (d)}m to generate the set of standard wavelet coefficients dm.
Referring to FIGS. 9 and 10, each reconstruction filter stage 163 and 164 includes a reconstruction filter stage 124 for the corresponding resolution level m. In accordance with the present invention, this reconstruction filter stage 124 is the same as the reconstruction filter stage 124 shown in FIG. 4 for the inverse wavelet transform system 120 of FIG. 3. Thus, this reconstruction filter stage 124 has the transfer functions P(z) and Q(z) for reconstructing the sets of standard scaling function and wavelet coefficients cm and dm at the lower resolution level m into the set of standard scaling function coefficients cm+1 at the next higher resolution level m+1.
Referring back to FIG. 8, the inverse wavelet transform system 160 further includes the same post-reconstruction filter 136 as that shown in FIG. 4 for the inverse wavelet transform system 120 of FIG. 3. Thus, as described earlier, the post-reconstruction filter 136 maps the set of standard scaling function coefficients cM into the set of reconstructed data samples fM.
As those skilled in the art will recognize, the concepts just described may be extended to a 2-D IWT and a corresponding 2-D inverse IWT. This extension is straight forward and therefore will not be described at this point. However, it must be noted here that the sequence of mapping coefficients {xcex4n} is large. Thus, unfortunately, the transfer function xcex2(z)xe2x88x921 is computationally complex and difficult to implement. For example, in the 2-D inverse IWT described in U.S. Pat. No. 5,600,373, the sequence of mapping coefficients {xcex4n} are provided as a banded matrix with many non-zero bands. This results in the 2-D inverse IWT being slow and inefficient when used to decompress 2-D image data.
In summary, the present invention comprises a wavelet transform system that implements a wavelet transform. Semi-orthogonal standard wavelets are used as the basic wavelets in the wavelet transform and related standard scaling functions are used as the basic scaling functions in the inverse wavelet transform. The standard scaling functions at a lower resolution level m are related to the standard scaling functions at a next higher resolution level m+1 by a first finite sequence of coefficients in a first two-scale relation. Similarly, the semi-orthogonal standard wavelets at the lower resolution level m are related to the standard scaling functions at the next higher resolution level m+1 by a second finite sequence of coefficients in a second two-scale relation.
The wavelet transform system includes a pre-decomposition filter. The pre-decomposition filter maps a set of original data samples into a set of dual scaling function coefficients at a resolution level m=M. The set of original data samples are given by a first function fm(x) that approximates a second function f(x) at the resolution level m=M.
The wavelet transform system further includes a decomposition filter that decomposes the set of dual scaling function coefficients at the resolution level M into a set of dual scaling function coefficients at a resolution level m=N and sets of dual wavelet coefficients at respective resolution levels m=M-1 to N. The decomposition filter includes a corresponding decomposition filter stage for each resolution level m=M to N+1 at which a decomposition is made.
The decomposition filter stage at each resolution level m decomposes a set of dual scaling function coefficients at the higher resolution level m into a set of dual scaling function coefficients and a set of dual wavelet coefficients at the next lower resolution level mxe2x88x921. In doing so, the first finite sequence of coefficients is applied to the set of standard scaling function coefficients at the higher resolution level m to generate the set of dual scaling function coefficients at the resolution level mxe2x88x921. Similarly, the second finite sequence of coefficients is applied to the set of standard scaling function coefficients at the higher resolution level m to generate the set of dual wavelet coefficients at the resolution level mxe2x88x921.
The present invention also comprises an inverse wavelet transform system that implements an inverse wavelet transform. The inverse wavelet transform corresponds to the wavelet transform implemented by the wavelet transform system just described. As in the wavelet transform, the semi-orthogonal standard wavelets are used as the basic wavelets in the inverse wavelet transform and the related standard scaling functions are used as the basic scaling functions in the inverse wavelet transform.
The inverse wavelet transform system includes a reconstruction filter that reconstructs a set of dual scaling function coefficients at a resolution level m=N and sets of dual wavelet coefficients at respective resolution levels m=N to Mxe2x88x921 into a set of dual scaling function coefficients at a resolution level M. The reconstruction filter includes a corresponding reconstruction filter stage for each resolution level m=N to Mxe2x88x921 at which a reconstruction is made.
The reconstruction filter stage for each resolution level m reconstructs a set of dual scaling function coefficients and a set of dual wavelet coefficients at the lower resolution level m into a set of dual scaling function coefficients at the next higher resolution level m+1. The reconstruction filter stage comprises a first mapping filter substage to apply a sequence of mapping coefficients to the set of dual scaling function coefficients at the resolution level m to generate a set of standard scaling function coefficients at the resolution level m. The reconstruction filter stage further includes a second mapping filter substage to apply the sequence of mapping coefficients to the set of dual wavelet coefficients at the lower resolution level m to generate a set of formatted wavelet coefficients at the resolution level m. Finally, the reconstruction filter stage includes a reconstruction filter substage to reconstruct the sets of standard scaling function and formatted wavelet coefficients at the lower resolution level m into the set of dual scaling function coefficients at the next higher resolution level m+1. This is done by applying a third finite sequence of reconstruction coefficients to the set of standard scaling function coefficients at the lower resolution level m and a fourth finite sequence of reconstruction coefficients to the set of formatted wavelet coefficients at the resolution level m. The third finite sequence of reconstruction coefficients is derived from the second finite sequence of reconstruction coefficients and the fourth finite sequence of reconstruction coefficients is derived from the first finite sequence of reconstruction coefficients.
The inverse wavelet transform system further includes a post-reconstruction filter. The post-reconstruction filter maps the set of dual scaling function coefficients at the resolution level M into a set of reconstructed data samples. The set of reconstructed data samples are also given by the first function fm(x), for the resolution level m=M.
As indicated previously, semi-orthogonal standard wavelets are used as the basic wavelets in the wavelet transform and the inverse wavelet transforms. Thus, the first and second finite sequences of reconstruction coefficients are not infinite sequences of coefficients that have been truncated.
Furthermore, in one embodiment of each decomposition filter stage of the wavelet transform system, downsampling is not used. Similarly, in one embodiment of each reconstruction filter stage of the inverse wavelet transform, upsampling is not used.
Additionally, in one embodiment of the pre-decomposition filter of the wavelet transform system, the pre-decomposition filter has a transfer function that is the sum of an all-zeros polynomial and an all-poles rational function. In this case, the pre-decomposition filter comprises parallel FIR and IIR filters. In another embodiment of the pre-decomposition filter, the pre-decomposition filter has a transfer function that is obtained from the orthogonal projection of the second function f(x) to the first function fm(x), for the resolution level m=M. In the case where this embodiment of the pre-decomposition filter is used in the wavelet transform system, a corresponding embodiment of the post-reconstruction filter is used in the inverse wavelet transform.